题目
分治（不带index辅助）
这个自己写的，空间复杂度较高
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(preorder.empty() || inorder.empty()) return NULL; //1. find root 3 //2. split into left & right 9 | 3 | 15 20 7 //3. 分治 int rootVal = preorder[0]; TreeNode* root = new TreeNode(rootVal); vector<int>::iterator inorderRootPos; inorderRootPos = find(inorder.begin(),inorder.end(),rootVal); vector<int> inorderLeft(inorder.begin(),inorderRootPos);//注意范围 vector<int> inorderRight(inorderRootPos+1,inorder.end()); // // inorder L ROOT R // // preorder Root L R int leftElemtNum = inorderRootPos-inorder.begin(); vector<int> preorderLeft(preorder.begin()+1,preorder.begin()+leftElemtNum+1); vector<int> preorderRight(preorder.begin()+leftElemtNum+1,preorder.end()); TreeNode* LeftChild = buildTree(preorderLeft,inorderLeft); TreeNode* RightChild = buildTree(preorderRight,inorderRight); root->left = LeftChild; root->right = RightChild; return root; } };- 时间复杂度:O(N)
- 空间复杂度:O(N+h)=O(N) [h为构造的树的高度,这里还有多次的创建数组的空间]